/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2018年08月19日
*   描    述：
*   Copyright (C) 2018 All rights reserved.
*   
================================================================*/


#include <iostream>

using namespace std;

/**
 * Definition of singly-linked-list:
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *        this->val = val;
 *        this->next = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param head: ListNode head is the head of the linked list 
     * @param m: An integer
     * @param n: An integer
     * @return: The head of the reversed ListNode
     */
    ListNode * reverseBetween(ListNode * head, int m, int n) {
        // write your code here
        if( !head || m == n )
            return head;

        int step = n - m;
        ListNode newhead = ListNode(-1);
        newhead.next = head;
        ListNode *prehead = &newhead;
        while( --m ){
            prehead = prehead->next;
        } 

        ListNode *cur = NULL;
        ListNode *p = prehead->next;
        while( step-- ){
            cur = p->next;
            p->next = cur->next;
            cur->next = prehead->next;
            prehead->next = cur;
        }

        return newhead.next;
    }
};
